Năm 1974, trong lần cùng bạn đi mua vé xem kịch khi Đoàn kịch Trung ương về biểu diễn, Hữu Mười thấy bảng thông báo tuyển diễn viên, điều khiến ông quyết định viết đơn ứng tuyên là thí sinh sẽ được chụp ba kiểu ảnh, bởi việc được chụp hình là điều không dễ dàng lúc bấy giờ.[2][1] Lá đơn của ông khi đó chỉ vỏn vẹn 6 dòng và suýt bị đuổi về vì cẩu thả và phải viết lại. Diên viên Phi Nga là người nhận ra tố chất diễn viên bên trong Hữu Mười, vượt qua vòng sơ tuyển, ông ra Hà Nội dự thi chung tuyển.[1] Khi tốt nghiệp ông là một trong 16 sinh viên trong lớp diễn viên khóa hai trường Điện ảnh Việt Nam cùng với các nghệ sĩ Bùi Cường, Minh Châu, Phương Thanh, Bùi Bài Bình, Quốc Trọng, Thanh Quý, Đào Bá Sơn,...[2]

Tốt nghiệp lớp diễn viên 1977, nghệ sĩ Hữu Mười về công tác tại Hãng phim truyện Việt Nam. Thời gian đầu ông thường hóa thân vào những vai thứ chính. Các bộ phim ông tham gia trong những năm đầu sự nghiệp như Khôn dại, Ngày ấy ở sông Lam, Phương án ba bông hồng.[1]

Năm 1982, Hữu Mười có được vai diễn để đời đầu tiên vào vai thầy giáo Thứ, nhân vật phỉnh theo nhà văn Nam Cao, trong phim Làng Vũ Đại ngày ấy.[1] Năm 1984, Đạo diễn Đặng Nhật Minh đưa đến cho ông kịch bane phim ông Bao giờ cho đến tháng Mười, vị đạo diễn quán triệt trước rằng không cho ông đóng vai thầy giáo giáo Khang vì lĩnh vực điện ảnh kị việc lặp lại trong diễn xuất. Sau đó vì không tìm được diễn viên phù hợp, Đặng Nhật Minh lại chọn Hữu Mười cho vai thầy giáo Khang,[3] vai diễn giúp ông có được giải Nam diễn viên chính xuất sắc tại Liên hoan Phim Việt Nam lần thứ 7. Năm 1987, Hữu Mười được Bộ Văn hóa cử đi học sang Liên Xô theo học ngành đạo diễn tại Trường Đại học Điện ảnh quốc gia Matxcova (VGIK) theo Hiệp định hợp tác Văn hoá - Giáo dục giữa hai nước.[4][5] Năm 1993, Hữu Mười tốt nghiệp và trở lại Hãng phim Truyện Việt Nam công tác.[2] Năm 1996, ông được đạo diễn Đặng Nhật Minh mời làm phó đạo diễn cho bôn phim Hà Nội mùa đông năm 46.[3]

Năm 1999, Nguyễn Hữu Mười mới có bộ phim điện ảnh đầu tiên do ông đạo diễn là Chiếc hộp gia bảo,[5] tiếp theo đó là các phim điện ảnh truyền hình cho các chương trình của Đài Truyền hình Việt Nam. Bộ phim 7 ngày làm vợ do ông đạo diễn từng được đề cử hạng mục Phim truyền hình ngắn tập của Giải Cánh diều 2004.[6] Hữu Mười bắt đầu tham gia công tác giảng dạy từ năm 2003, ông từng nhậm chức trưởng Khoa truyền hình, trường Đại học sân khấu Điện ảnh Hà Nội.[1]

Năm 2011, Nguyễn Hữu Mười mạnh dạn nhận đạo diễn bộ phim chiến tranh Mùi cỏ cháy, sau khi kịch bản phim bị nhiều đạo diễn khác từ chối vì kinh phí cho phim quá eo hẹp.[7][8] Bộ phim sau đó chiến thắng 4 giải trong hạng mục phim truyện điện ảnh tại giải Cánh diều 2011 trong đó có giải quan trọng nhất, Cánh Diều Vàng cho phim truyện điện ảnh.[9] Mùi cỏ cháy cũng chiến thằng hạng mục phim điện ảnh tại Liên hoan phim Việt Nam lần thứ 17 với giải Bông sen Bạc và Biên kịch xuất sắc.[10]